\documentclass[supercite]{Experimental_Report}

\title{~~~~~~函数式编程原理课程报告~~~~~~}
\author{崔昊阳}
\school{计算机科学与技术学院}
\classnum{CS2104}
\stunum{U202115415}
\instructor{顾琳}
\date{2023年10月21日}

\usepackage{algorithm, multirow}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{mathtools}
\usepackage{subcaption}
\usepackage{xltxtra}
\usepackage{bm}
\usepackage{tikz}
\usepackage{tikzscale}
\usepackage{pgfplots}
\usepackage{makecell}
\usepackage{listings}
\lstset{
    backgroundcolor = \color{white},    % 背景色
    basicstyle = \small\ttfamily,           % 基本样式 + 小号字体
    rulesepcolor= \color{black},             % 代码块边框颜色
    breaklines = true,                  % 代码过长则换行
    numbers = left,                     % 行号在左侧显示
    numberstyle = \small,               % 行号字体
    keywordstyle = \color{blue}\bfseries,      % 关键字颜色
	identifierstyle=\color{purple}, 		% 标识符颜色
    commentstyle =\color{green},        % 注释颜色
    stringstyle = \color{green},          % 字符串颜色
    frame = shadowbox,                  % 用（带影子效果）方框框住代码块
    showspaces = false,                 % 不显示空格
    columns = flexible,                    % 字间距固定
}

\pgfplotsset{compat=1.16}

\newcommand{\cfig}[3]{
  \begin{figure}[htb]
    \centering
    \includegraphics[width=#2\textwidth]{images/#1.tikz}
    \caption{#3}
    \label{fig:#1}
  \end{figure}
}

\newcommand{\sfig}[3]{
  \begin{subfigure}[b]{#2\textwidth}
    \includegraphics[width=\textwidth]{images/#1.tikz}
    \caption{#3}
    \label{fig:#1}
  \end{subfigure}
}

\newcommand{\xfig}[3]{
  \begin{figure}[htb]
    \centering
    #3
    \caption{#2}
    \label{fig:#1}
  \end{figure}
}

\newcommand{\rfig}[1]{\autoref{fig:#1}}
\newcommand{\ralg}[1]{\autoref{alg:#1}}
\newcommand{\rthm}[1]{\autoref{thm:#1}}
\newcommand{\rlem}[1]{\autoref{lem:#1}}
\newcommand{\reqn}[1]{\autoref{eqn:#1}}
\newcommand{\rtbl}[1]{\autoref{tbl:#1}}

\algnewcommand\Null{\textsc{null }}
\algnewcommand\algorithmicinput{\textbf{Input:}}
\algnewcommand\Input{\item[\algorithmicinput]}
\algnewcommand\algorithmicoutput{\textbf{Output:}}
\algnewcommand\Output{\item[\algorithmicoutput]}
\algnewcommand\algorithmicbreak{\textbf{break}}
\algnewcommand\Break{\algorithmicbreak}
\algnewcommand\algorithmiccontinue{\textbf{continue}}
\algnewcommand\Continue{\algorithmiccontinue}
\algnewcommand{\LeftCom}[1]{\State $\triangleright$ #1}

\newtheorem{thm}{定理}[section]
\newtheorem{lem}{引理}[section]

\colorlet{shadecolor}{black!15}

\theoremstyle{definition}
\newtheorem{alg}{算法}[section]

\def\thmautorefname~#1\null{定理~#1~\null}
\def\lemautorefname~#1\null{引理~#1~\null}
\def\algautorefname~#1\null{算法~#1~\null}

\begin{document}

\maketitle

\clearpage

\pagenumbering{Roman}

\tableofcontents[level=2]

\clearpage

\pagenumbering{arabic}

\section{函数式语言家族成员调研}
\subsection{总述}
在计算机科学中，函数式编程是一种通过构造函数来实现计算的编程范式。
函数式编程中的"函数"一词指的是从输入值到输出值的数学意义上的映射，它在给定相同的输入时，总是产生相同的输出。
同时，除了返回一个值之外，函数不应该有任何“副作用”\cite{TPFP}。
在函数式编程中，函数被视为一等公民，这意味着它们可以绑定到名称（包括本地标识符），作为参数传递，并从其他函数返回，就像任何其他数据类型一样。
为了支持函数式编程这一编程范式，人们设计了多种函数式语言。下面，我们将介绍函数式语言的发展历史及兴衰、一些具有代表性的函数式语言以及函数式语言的共同特点、优势和不足以及未来展望。
\subsection{函数式语言的发展历史及兴衰}
函数式语言的发展经历了几个关键的时期：$\lambda$ 演算时期、早期函数式语言时期和现代函数式语言时期\cite{CEAFPL}。
函数式语言的发展时间轴及它们之间的关系如图\ref{函数式语言时间轴}和图\ref{函数式语言关系}所示。下面将详细叙述这几个时期代表性函数式语言的特点。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.30]{images/函数式语言时间轴.pdf}
		\caption{函数式语言时间轴}
		\label{函数式语言时间轴}
	\end{center}
\end{figure}
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/函数式语言关系.pdf}
		\caption{函数式语言的关系树}
		\label{函数式语言关系}
	\end{center}
\end{figure}
\subsubsection{$\lambda$ 演算时期}
$\lambda$ 演算是 20 世纪 30 年代由阿伦佐·邱奇提出，作为一个研究有效可计算函数的数学性质的工具而发展起来的。
它由一个单一的转换规则($\beta$-规约)和一个单一的函数定义方案组成。$\lambda$ 演算具有普适性，即任何可计算的函数都可以用这种数学工具来表达和计算。
这样以来，它就和图灵机等价，成为不同于图灵机的另一种抽象的计算方式，这也使得函数式语言不依赖于冯·诺依曼体系结构的计算机\cite{ATILC}。

$\lambda$ 演算为函数式编程语言家族提供了强大的理论基础。它虽然不是一种真正意义上的函数式编程语言，但可视为所有函数式语言的祖先。

\subsubsection{早期函数式语言时期}
20 世纪 50 年代至 20 世纪 70 年代，出现了一批以 Lisp 语言、ML 语言为代表的早期函数式语言。这些函数式语言包括 Lisp, Iswim, APL, FP, ML 等\cite{CEAFPL}。
这些语言都是以 $\lambda$ 演算为基础来设计的。它们也都具有函数式编程的特征：函数作为一等公民、大量使用递归、支持高阶函数等。这些共同之处反映了函数式编程语言的核心原则。
但和现代函数式语言相比，早期函数式语言普遍存在以下的不足之处：
\begin{enumerate}
  \item 动态类型系统：早期函数式编程语言通常具有弱类型或动态类型系统，即变量可以在运行时绑定到不同的类型。而现代函数式编程语言倾向于采用静态类型系统，通过类型推断和类型约束来提供更强的类型安全性和编译时错误检查。
  \item 惰性求值支持少：早期函数式编程语言不普遍支持惰性求值。而现代函数式编程语言（尤其是 Haskell）广泛采用惰性求值，允许更高效地处理无限数据流和延迟计算。
  \item 副作用处理宽松：早期函数式编程语言对副作用的处理相对宽松，允许在函数中修改外部状态。而现代函数式编程语言（特别是纯函数式编程语言如 Haskell）更强调函数的纯粹性，避免副作用以提高代码的可读性和可维护性。
\end{enumerate}

\subsubsection{现代函数式语言时期}
20 世纪 70 年代至 80 年代，出现了一批以 SASL 语言、Haskell 语言为代表的现代函数式语言。这些函数式语言包括 SASL, Miranda, Hope, SML, Haskell 等\cite{CEAFPL}。
这些语言除了拥有函数式编程的核心特点之外，还存在下列显著特点，这也是区分它们和早期函数式语言的标志\cite{CEAFPL}。
\begin{enumerate}
  \item 完善的高阶函数支持：现代函数式语言对高阶函数有了更完善的支持。它们鼓励函数组合，即通过将多个函数按照特定的顺序组合在一起形成新的函数，从而实现代码的复用和组合性。
  \item 完善的惰性求值支持：现代函数式语言支持惰性求值，即表达式只在需要时才会被求值。惰性求值可以带来一些优势，如支持处理无限数据结构、延迟计算和避免不必要的计算开销。
  \item 采用静态类型：大多数现代函数式语言用静态类型系统，即在编译时进行类型检查，并在类型不匹配时产生错误。静态类型系统可以提供更强的类型安全性和编译时错误检查，帮助开发者在早期发现和修复潜在的类型错误。
  \item 强大的模式匹配机制：大多数现代函数式语提供了强大的模式匹配机制，用于处理数据结构的解构和匹配。它们也支持代数数据类型，允许用户定义复杂的数据类型和模式匹配规则。
\end{enumerate}

\subsubsection{函数式语言的兴衰史}
函数式编程的兴起和衰落经历了一系列的演变和变革\cite{TFRFP}。在计算机科学的早期阶段，阿隆佐·邱奇和艾伦·图灵提出的 $\lambda$ 演算和图灵机的概念奠定了函数式编程的理论基础。之后，Lisp 在 1958 年被提出。Lisp 提出后，
一大批早期函数式编程语言相继问世，函数式编程迎来了其兴起阶段。

在 20 世纪 70 年代到 80 年代，面向过程编程和命令式编程开始占据主导地位。
这些编程范式更加注重过程和指令的顺序执行，而非函数的组合和变换，函数式编程开始衰落。
同时，面向对象编程开始兴起，将重点放在数据和对象的封装上，这使得函数式编程的影响力受到了一定的冲击。
在 1990 年到 2010 年之间，Java 等面向对象语言的流行进一步导致了函数式编程语言的衰落。
许多开发者开始采用面向对象编程的思维方式，而函数式编程逐渐被边缘化。

但是，2010年左右，JavaScript 的崛起引发了函数式编程的复兴。
函数式编程的概念开始在 JavaScript 社区中传播，诸如纯函数、不可变性、高阶函数、柯里化等概念逐渐流行起来。
函数式编程的库和框架如 React 和 Redux 的出现进一步推动了函数式编程在前端开发中的应用。
现代的编程语言往往将函数式编程的特性融入其中，
例如 Java 8 引入的 Lambda 表达式和流式 API，Python 中的函数式编程库等。

经历过数次兴起和衰落后，函数式编程思想逐渐和其它编程思想融合，为开发者提供了另一种选择和思考方式。
在今天，函数式编程依然被广泛应用于金融、科学计算等领域。
在位于 IEEE Spectrum 2023 年度编程语言榜单前十名的语言中\cite{TTPL}，有 7 种语言对函数式编程有完善的支持，如图\ref{编程语言排行榜前十名}。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/编程语言排行榜前十名.png}
		\caption{绿色框框住的语言对函数式编程有完善的支持}
		\label{编程语言排行榜前十名}
	\end{center}
\end{figure}

\subsection{函数式语言具体介绍}
由于函数式语言的种类极其丰富，我们无法一一介绍。所以，我们结合 \textit{22 BEST Functional Programming Languages In 2023}\cite{2BFPLI}，选择了
一些具有代表性的主流函数式语言进行具体介绍。我们将要介绍的语言如图\ref{函数式语言介绍}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/函数式语言具体介绍.pdf}
		\caption{我们将要介绍的函数式语言}
		\label{函数式语言介绍}
	\end{center}
\end{figure}

\subsubsection{Lisp 语言}
Lisp 是最早的包含函数式程序设计元素的程序设计语言。它由约翰·麦卡锡于1958年发明。
Lisp 借鉴了阿隆佐·邱奇提出的用于匿名函数的表示法，它和一些简单的运算符结合，从而成为了一个具备图灵完备性的语言\cite{RFSETCM}。Lisp 的徽标如图\ref{Lisp}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/Lisp.jpg}
		\caption{Lisp 的徽标}
		\label{Lisp}
	\end{center}
\end{figure}

% 特点 / 创意
Lisp是一种面向表达式的编程语言，其独特之处在于它不区分表达式和语句。所有的代码和数据都被写成表达式。
当一个表达式被求值时，它会产生一个值，然后这个值可以作为其他表达式的输入。每个值可以是任何数据类型的。
Lisp 中有两种类型的表达式：符号表达式，也称为 S-表达式，它反映了代码和数据的内部表示；以及元表达式，也称为 M-表达式，它是与 S-表达式对应的用类似数学符号表示的函数。
由于表达式给予了该语言巨大的灵活性，Lisp 函数被写成列表，它们可以完全像数据那样处理。这使得编写能够操纵其他程序的程序变得非常容易。许多 Lisp 方言使用宏系统来利用这个特性，这使得语言扩展几乎没有限制。

% 数据类型
在 Lisp 中，只有两种基本的数据类型：原子和列表。
列表是有序元素的集合，每个元素要么是原子，要么是另一个列表。
而原子要么是数字，要么是符号。原子是不可变的，且每个原子都是独一无二的。
如果在代码的不同位置使用完全相同的符号，它们代表同一个对象。
但每个列表都是一个独立的对象，可以独立于其他列表进行更改，并且可以通过比较操作符来区分不同的列表。

% 函数
在 Lisp 中，函数的定义方法如下：
\begin{lstlisting}[language=lisp]
  (defun function-name (parameter-list)
  "Function documentation string"
  (if (condition)
      (statement1)
    (statement2)))
\end{lstlisting}
其中，defun 是 Lisp 语言中用于定义函数的关键词，function-name 是函数的名称，
parameter-list 是函数的参数列表。
函数定义中的第一行是函数的文档字符串，用于描述函数的作用和用法。

\subsubsection{Clojure 语言}
Clojure 是 Lisp 语言在 Java 平台上的方言。它由里奇·希基于 2007 年发布\cite{IPLC}。
Clojure 是一门适合函数式编程的现代 Lisp 方言，它既与已建立的 Java 平台共生又适合并发编程。
Clojure 的徽标如图\ref{Clojure}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/Clojure.png}
		\caption{Clojure 的徽标}
		\label{Clojure}
	\end{center}
\end{figure}

在 Clojure 中，状态的概念在管理数据和计算中起着重要的作用。
Clojure 采用了不可变的数据模型，其中数值是不可变的，对数据的任何操作都会创建新的值，而不是修改现有的值。
这种不可变性确保了线程安全，并简化了对代码的推理。然而有时我们需要处理可变状态，例如处理 I/O 操作或共享资源。
为了处理这些情况，Clojure 提供了可变的引用类型。这些类型是 "refs"、"agents"和"atoms"。

正如上文所述，Clojure 除了支持 Lisp 中的所有类型之外，还添加了可变的引用类型。
"Refs"用于协调和同步的状态更新。它们允许多个事务以受控的方式对共享状态进行操作。
"Refs"确保对状态的更改是原子和一致的，并提供了处理冲突和重试的内置机制。
而"Agents"则用于非协调和异步的状态更新。它们允许对状态进行独立且并发的操作，而无需显式地协调它们。
"Agents"维护自己的状态，并异步地将更改应用于它们。它们适用于不需要即时一致性，而可以接受最终一致性的场景。
"Atoms"提供了一种更简单的可变状态管理方式。
它们本质上是单一的、隔离的值，可以以原子方式进行更新。
"Atoms"适用于需要以线程安全的方式更新状态，而无需在多个线程之间进行协调的情况。

在 Clojure 中，函数的定义方法如下：
\begin{lstlisting}
  ;; 一个典型的Clojure程序的入口
  (defn -main ; 函数名
    [& args] ; 参数向量 (`&`表示可变参数)
    (println "Hello, World!")) ; 函数体
\end{lstlisting}

\subsubsection{ML 语言}
ML 语言是 ML 语言家族的第一个语言。
在 20 世纪 70 年代早期，ML 语言由爱丁堡大学的罗宾·米尔纳及他人提出，用于在LCF定理证明器中开发证明策略\cite{HME}。

ML 语言提供了模式匹配、垃圾回收、指令式编程、传值调用和柯里化等功能，可广泛应用于编程语言研究。
作为少数经过全面规范和形式语义验证的语言之一，它在其他形式语言上的操作中发挥着重要作用。
其类型系统和模式匹配特性使其特别适用于编译器构建、自动化定理证明和形式验证等领域。

不同于 Lisp，ML 语言提供了丰富的数据类型。下面简要列出几种常见类型。
\begin{enumerate}
  \item 基本数据类型：包括整数（int）、浮点数（real）等。
  \item 列表类型（List）：表示一个有序的元素序列，可以包含不同类型的元素，并使用方括号括起来。
  \item 元组类型（Tuple）：类似于列表类型，但元素的数量和类型是固定的，并使用圆括号括起来。
  \item 函数类型（Function）：表示函数的类型，包含参数类型和返回值类型的描述。
\end{enumerate}
以上数据类型经组合和嵌套可以构建更复杂的数据结构和类型表达。
ML 的类型系统基于 Hindley-Milner 类型推论，能够自动推断表达式的类型，从而提供类型安全和静态类型检查的特性。

在 ML 中，函数的定义方法如下：
\begin{lstlisting}[language=ml]
  fun functionName (parameter1: type1, parameter2: type2, ...)
  : returnType =
    (* 函数体 *)
\end{lstlisting}
其中，functionName 是函数名称，parameter1: type1, parameter2: type2, ...是函数的参数和类型，
returnType 是函数的返回类型。
\subsubsection{F\# 语言}
F\# 是由微软发展的为 .NET 语言提供运行环境的程序设计语言。
F\# 是基于 OCaml 的，而 OCaml 是基于 ML 语言的。有时，F\# 和 OCaml 的程序可以交互编译。
F\# 的徽标如图\ref{F}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/F.png}
		\caption{F\# 的徽标}
		\label{F}
	\end{center}
\end{figure}

F\# 支持函数作为一等公民，可以将函数赋值给变量、作为参数传递和返回值返回。
它提供了丰富的函数式编程工具，如高阶函数、不可变数据和递归等，使得编写简洁、可组合的函数式代码成为可能。
同时，F\# 具有强大的类型推断和模式匹配的能力。F\# 还支持惰性求值，即只在需要时才计算表达式的值。
这种惰性计算机制可以提高性能，并允许处理无限序列和大数据集。

F\# 同样拥有丰富的类型系统。其拥有的类型如表\ref{F支持的类型}所示。
\begin{table}[H]
  \centering
  \caption{F\# 支持的类型}
  \resizebox{\linewidth}{!}{
    \begin{tabular}{ccc}
    \toprule
    \textbf{数据类型}  & \textbf{名称}    & \textbf{含义} \\\hline
    \multirow{6}[0]{*}{基本数据类型} & int   & 32 位整型 \\
          & int64 & 64 位整型 \\
          & float & 32 位浮点型 \\
          & double & 64 位浮点型 \\
          & bool  & 布尔类型 \\
          & char  & 字符类型 \\\hline
    \multirow{4}[0]{*}{集合类型} & list  & 列表类型，表示一个不可变的有序集合 \\
          & array & 数组类型，表示一个固定大小的有序集合 \\
          & seq   & 序列类型，表示一个惰性计算的序列。 \\
          & map   & 映射类型，表示键值对的集合 \\\hline
    元组类型  & ('a * 'b) & 使用逗号分隔的值的有序组合 \\\hline
    记录类型  & \{ foo: string; bar: int \} & 使用命名字段的结构化数据类型 \\\hline
    \multirow{3}[0]{*}{代数数据类型} & Discriminated Union & \makecell{标签联合类型，\\使用不同的标签和关联的值来定义多个可能的选择} \\
          & Option & \makecell{选项类型，\\表示一个可能存在或可能为缺失的值，用于处理可能为空的情况} \\
          & Result & \makecell{结果类型，\\表示一个操作的结果，可以是成功的值或错误的信息。} \\\hline
    函数类型  & fun   & \makecell{函数类型，\\表示接受一个或多个参数并返回结果的函数。} \\\bottomrule
    \end{tabular}}
  \label{F支持的类型}
\end{table}

在 F\# 中，函数的定义方法如下：
\begin{lstlisting}
  let functionName parameter1 parameter2... =
    (* 函数体 *)
\end{lstlisting}
其中，let 关键字用于定义一个函数，functionName 表示函数名称，parameter1 parameter2 ...是函数的参数列表。

\subsubsection{SML 语言}
Standard ML 是 ML 的现代方言。它最初于 1973 年由罗宾·米尔纳等人开发，后来在 1983 年发布了标准化版本。和其它 ML 家族的方言不同的是，\textit{The Definition of Standard ML}\cite{TDSM} 给出了
Standard ML 的类型规则和操作语义。SML 语言广泛流行于编译器作者和编程语言研究者和自动定理证明研究者之中，但在工业界的应用较少。

Standard ML 语言支持的类型较为丰富，但少于 F\#。其支持的类型如表\ref{SML支持的类型}所示。
\begin{table}[htb]
  \centering
  \caption{SML 语言支持的类型}
  \resizebox{\linewidth}{!}{
    \begin{tabular}{ccc}
    \toprule
    \textbf{数据类型} & \textbf{名称} & \textbf{含义} \\\hline
    基本数据类型 & int   & 整型 \\
          & real  & 实数类型 \\
          & char  & 字符类型 \\
          & string & 字符串类型 \\\hline
    列表类型  & 'a list & 表示一个列表 \\
    元组类型  & 'a * 'b & 表示一个有序对 \\
    函数类型  & 'a -> 'b & 表示一个函数 \\
    选项类型  & 'a option & 表示可能存在或可能为缺失的值 \\
    记录类型  & \{ foo: 'a, bar: 'b, \} & 表示具有命名字段的记录 \\
    标签联合类型 & Constructor & 表示具有不同标签的值的联合类型 \\
    引用类型  & 'a ref & 表示可变的单个位置 \\\bottomrule
    \end{tabular}}
  \label{SML支持的类型}
\end{table}


在 SML 中，函数的定义方法和 F\# 中的定义方法基本相同，如下。
\begin{lstlisting}[language=ml]
  fun functionName parameter1 parameter2 ... = 
    (* 函数体 *)
\end{lstlisting}
其中，fun 关键字用于定义一个函数，functionName 表示函数名称，parameter1 parameter2 ...是函数的参数列表。

\subsubsection{Scala 语言}
Scala 是一门运行于 Java 虚拟机上的多范式的编程语言，设计初衷是要集成面向对象编程和函数式编程的各种特性。
Scala 的徽标如图\ref{Scala}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/Scala.png}
		\caption{Scala 的徽标}
		\label{Scala}
	\end{center}
\end{figure}

与其他函数式编程语言相比，Scala 具有诸多独特之处。
首先，Scala 运行在 Java 虚拟机上，并且与 Java 代码可以无缝互操作。这使得 Scala 成为一个可逐步采用的语言。
其次，Scala 不仅支持函数式编程，还完全兼容面向对象编程。
它将面向对象和函数式编程的概念融合在一起，可以使用类、对象、继承等面向对象的特性，
同时还能利用高阶函数、不可变性和模式匹配等函数式编程的特性。
最后，Scala 还支持插值字符串，可以在字符串中直接引用变量或表达式，并在编译时进行求值。
这使得字符串拼接和格式化更加简洁和安全。
同时，Scala 还具备创建领域特定语言（DSL）的能力，通过强大的语言特性可以为特定领域编写高度表达力和易用性的代码。

Scala 所支持的数据类型和 F\#, SML 等语言相似，在此不再赘述。在 Scala 中，函数的定义方法如下：
\begin{lstlisting}[language=scala]
def functionName(parameter1: Type1, parameter2: Type2, ...): 
ReturnType = 
{
// 函数体
// 可以包含多条语句
// 最后一条表达式的值将作为函数的返回值
}
\end{lstlisting}
其中，functionName 是函数的名称，parameter1、parameter2 等是函数的参数名和对应的参数类型，ReturnType 是函数的返回类型。

\subsubsection{Haskell 语言}
Haskell 是一种标准化的，通用的纯函数式编程语言，它支持惰性求值，并且是一门强静态类型的语言\cite{AHHBLC}。
Haskell 的徽标如图\ref{Haskell}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/Haskell.png}
		\caption{Haskell 的徽标}
		\label{Haskell}
	\end{center}
\end{figure}

Haskell 还支持模式匹配、列表解析、类型类和类型多态等特性。
作为一门纯函数式编程语言，Haskell中的函数基本上没有副作用。
副作用通过特定的类型来表达，这些类型与函数类型是独立的。
纯函数可以操作并返回可执行的副作用的类型，但是无法执行它们。
只有用于表达副作用的类型才能执行这些副作用，Haskell通过这种方式来表达其他语言中的非纯函数。
这样的设计使得Haskell在函数式编程领域具有独特的优势。

作为一门现代函数式语言，Haskell 的数据类型十分丰富。Haskell 的数据类型间的关系图如图\ref{Haskell数据类型间的关系}所示。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.60]{images/Haskell数据类型间的关系.png}
		\caption{Haskell数据类型间的关系}
		\label{Haskell数据类型间的关系}
	\end{center}
\end{figure}

在 Haskell 中，函数的定义方法如下：
\begin{lstlisting}[language=haskell]
functionName :: Type1 -> Type2 -> ... -> ReturnType
functionName parameter1 parameter2 ... = functionBody
\end{lstlisting}
其中，functionName 是函数的名称，Type1、Type2 等是参数的类型，ReturnType 是函数的返回类型，functionBody 是函数的具体实现。

\subsection{函数式语言的共同特点}
经过阅读相关文献，我们发现，函数式语言具有如下的共同特点\cite{TPFP}\cite{SPT}。图\ref{函数式语言的特点}是这些特点和相应的解释。
\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.36]{images/函数式语言的特点.pdf}
		\caption{函数式语言的共同特点}
		\label{函数式语言的特点}
	\end{center}
\end{figure}

\subsection{函数式语言的优势以及不足}
函数式编程思想和函数式语言相比于其它编程思想和语言，具有突出的优势\cite{WFPM}。第一，函数式语言易于推理和理解。函数式编程鼓励编写纯函数，这些函数没有副作用，并且输出只依赖于输入。这种纯函数的特性使得代码更易于推理和理解。由于函数之间没有隐藏的状态依赖关系，函数可以独立于上下文进行测试和调试，使得代码更加可靠和可维护。
第二，函数式语言可复用和模块化性能较好。函数式编程鼓励使用高阶函数和函数组合来构建代码。这种函数组合性使得函数可以在不同的上下文中进行复用，通过将现有函数组合成新的函数，可以轻松构建复杂的功能。函数式编程的模块化特性使得代码更易于扩展和维护，同时也促进了代码的重用性。
第三，函数式语言具有更好的并发和并行性。函数式编程的纯函数特性使得函数之间没有共享的可变状态，从而避免了竞态条件和数据竞争。这使得函数式代码更容易进行并发和并行处理。由于函数是无副作用的，可以安全地在多个线程或进程中执行，从而提高了系统的并发性能。
第四，函数式语言具有更好的容错性。函数式编程鼓励使用不可变数据结构，并通过函数组合来构建复杂的逻辑。不可变数据结构的使用消除了意外的数据修改，减少了代码中出现的错误。函数组合性使得代码更容易进行推理和调试，帮助发现和修复潜在的错误。这些特性共同提升了函数式编程的容错性。
第五，函数式语言具有更好的可测试性。函数式编程的纯函数特性使得函数的输出只由输入决定，不依赖于外部状态。这种特性使得函数更易于测试，可以通过提供不同的输入来验证函数的行为。纯函数的可测试性有助于编写高质量的测试用例，提高代码的可靠性和稳定性。

与此同时，函数式编程思想和函数式语言也有一些不足之处\cite{ABOFPL}。
例如，因为函数式语言提倡纯函数且大多数交互式应用依赖于使用请求和响应方法，使用函数式语言进行交互式应用的开发的难度较大。
在像 Haskell 这样的纯函数式语言中，执行 I/O 的计算被认为是不纯的，
需要像 list 那样的结构来隔离这些可能产生副作用的计算。
同时，在纯函数式语言中，我们难以实现需要长时间运行的程序。因为这种程序通常需要一个死循环。
现在的大多数应用程序都是围绕从数据库等数据源中检索到的数据而展开的，
这种数据在面向对象的语言中比在函数式语言中更容易处理。
另外，与命令式程序设计语言相比，函数式程序设计语言的学习成本也普遍较高。

\subsection{函数式语言的未来展望}
在\textit{A Brief Overview of Functional Programming Languages}\cite{ABOFPL} 一文中，
作者提到了函数式语言和函数式编程思想的未来发展方向。
他们认为，在未来更多的工作会致力于将函数式编程概念集成到现有的编程语言中，而且这些工作主要以开源的方式驱动。
上述工作将致力于在现有编程语言的内部开发一个支持函数式编程的模块，或者通过库对语言进行支持函数式编程的补充。
同时，人们也会将函数式编程引入各种平台，如 Elm 在 Web 开发环境中引入函数式编程。
并且，函数式语言也有望在工业应用中取得进一步的进展。
\newpage
\section{上机实验心得体会}
在上机实验中，我通过自己动手编写 SML 语言代码完成相应任务，提高了自己对函数式编程思想和函数式语言应用的了解程度。
下面我将具体介绍 3 个我印象较为深刻的实验。
\subsection{实验2\_4: reverse 函数}
\subsubsection{实验要求}
编写函数 reverse 和 reverse2。

要求：

函数类型均为：int list->int list，功能均为实现输出表参数的逆序输出；

函数reverse不能借助任何帮助函数；函数reverse2可以借助帮助函数，时间复杂度为O(n)。
\subsubsection{解题思路}
对于 reverse1 函数，当输入列表不为空时，我们每次从输入的列表中拿出首元素放到已反转的剩余列表的最后即可。

对于 reverse2 函数，由于要求 work 为$O(n)$，我们需要引入帮助函数。帮助函数接收两个参数，
分别是还未反转的列表和已完成反转的列表。当未反转的列表不为空时，
我们从未反转的列表中取出首元素放在已完成反转的列表的表头即可。
\subsubsection{通关代码}
\begin{lstlisting}[language=ml]
(*REQUIRES: 输入任意类型元素的列表*)
(*ENSURES: 输入列表的反转*)
fun reverse([]) = []
|reverse(a::L) = reverse(L) @ [a]
(*REQUIRES: 输入任意类型元素的列表*)
(*ENSURES: 输入列表的反转*)
fun reverse2(L) = 
let
    fun revHelper([], ret) = ret
        |revHelper(p::params, ret) = revHelper(params, p::ret)
in
    revHelper(L, [])
end;
\end{lstlisting}
\subsubsection{感悟}
通过这个实验，我对函数式编程中帮助函数的应用有了更深入地了解。通过帮助函数，我们可以在需要递归的主函数
中完成较为复杂的功能，从而可以完成优化函数的时间复杂度等任务。

\subsection{实验3\_1: listToTree}
\subsubsection{实验要求}
编写函数 listToTree: int list -> tree，将一个表转换成一棵树。

调用课堂上讲解的 split 函数，list 的第一个元素为 root
\subsubsection{解题思路}
我们可以使用递归的思想来构建一棵树。首先，我们选择一个根节点，再把剩余的列表元素送入课上实现的 split 函数进行分割。
最后递归调用建树函数使用分割结果构建左右子树即可。
\subsubsection{通关代码}
\begin{lstlisting}[language=ml]
fun split [ ]  = ([ ], [ ]) 
  | split [x] = ([ ], [x])
  | split (x::y::L) =
let val (A, B) =split L
in (x::A, y::B) 	
end;
datatype tree = Empty | Br of tree * int * tree;
(*REQUIRES: 输入整数列表*)
(*ENSURES: 一棵二叉树*)
fun listToTree ([] : int list) : tree = Empty
| listToTree (x::l) = 
  let
      val (L1, L2) = split(l)
  in
      Br(listToTree L1, x, listToTree L2)
  end;
\end{lstlisting}

\subsubsection{感悟}
通过这次实验，我体会到了递归在函数式编程中的重要作用。通过递归，我们可以使得复杂的编程任务变得简单而易于理解。

\subsection{实验4\_4: exists}
\subsubsection{实验要求}
编写函数：

    exists: (int -> bool) -> int list -> bool

要求：对函数p: int -> bool, 整数集L: int list,有：

exist p L =>* true if there is an x in L such that p x=true;

exits p L =>* false otherwise.
\subsubsection{解题思路}
我们可以通过构建高阶函数来解决这个问题。若传入列表非空，我们首先应用函数 f 到当前元素 x，如果结果为 true，则返回 true，表示存在满足条件的元素。
否则，递归调用 exists 函数，将函数 f 和剩余的列表作为参数传递，继续在剩余的元素中查找满足条件的元素。
递归的终止条件是当输入列表为空时，递归停止，返回 false，表示没有找到满足条件的元素。
\subsubsection{通关代码}
\begin{lstlisting}[language=ml]
(*REQUIRES: 输入一个 int -> bool 的函数和一个整数列表*)
(*ENSURES: 若列表中存在元素使得 f 为 true，则返回 true；否则返回 false*)
fun exists f [] = false
|exists f (x::L) = f(x) orelse exists f L;
\end{lstlisting}
\subsubsection{感悟}
通过这个实验，我增进了对函数式编程中的高阶函数的理解。在函数式编程中，函数是一等公民，所以我们可以
以远比如 C 语言这种面向过程的语言简单的方式来实现高阶函数，
从而使某些任务，例如利用相同函数处理一批数据，得到极大地简化。
\newpage
\section{课程建议和意见}
通过本次函数式编程原理课程，我了解了函数式编程这一编程思想。深刻认识到了函数式编程的优势和应用方式。
这门课程不仅让我掌握了函数式编程的基本原理和常用技术，还提高了我的编码水平和思维能力。
这门课程的授课老师经验丰富，讲解清晰易懂，让我对函数式编程有了更深入的理解和掌握。
同时，课程内容涵盖了函数式编程的基本概念、理论。本次课程的实践环节也使我在实际项目中能够更好地应用函数式编程的思想和原则。
总体来说，通过本次课程，我的收获颇丰。

我对本次函数式编程原理课程提出以下的建议：
\begin{enumerate}
  \item 在理论课环节，适当增加一些函数式语言和其它语言的对比。这样有利于同学们更好地了解函数式编程思想的特点，也有利于降低同学们在写实验报告第一章查找并阅读文献时的困难程度。
  \item 在实践课环节，实验三的难度相较于实验二有较大的提升。建议在实验三增加一些前置的简单关卡使难度提升更加平稳。
\end{enumerate}


\bibliography{Experimental_Report}
\setcounter{secnumdepth}{0}

\end{document}